<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<!-- DW6 -->
<head>
<!-- Copyright 2005 Macromedia, Inc. All rights reserved. -->
<title>Text</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link rel="stylesheet" href="../mm_health_nutr.css" type="text/css">
<script language="javascript">
//--------------- LOCALIZEABLE GLOBALS ---------------
var d=new Date();
var monthname=new Array("January","February","March","April","May","June","July","August","September","October","November","December");
//Ensure correct for language. English is "January 1, 2004"
var TODAY = monthname[d.getMonth()] + " " + d.getDate() + ", " + d.getFullYear();
//---------------   END LOCALIZEABLE   ---------------
</script>
</head>
<body bgcolor="#F4FFE4">
<table width="100%" border="0" cellspacing="0" cellpadding="0">
  <tr bgcolor="#D5EDB3">
    <td colspan="2" rowspan="2">&nbsp;</td>
    <td width="494" height="50" id="logo" valign="bottom" align="center" nowrap>Blancas y Negras</td>
    <td width="103">&nbsp;</td>
  </tr>

  <tr bgcolor="#D5EDB3">
    <td height="19" id="tagline" valign="top" align="center">Grupo 15</td>
	<td width="103">&nbsp;</td>
  </tr>

  <tr>
    <td colspan="4" bgcolor="#5C743D"><img src="mm_spacer.gif" alt="" width="1" height="2" border="0"></td>
  </tr>

  <tr>
    <td colspan="4" bgcolor="#99CC66" background="mm_dashed_line.gif"><img src="mm_dashed_line.gif" alt="line decor" width="4" height="3" border="0"></td>
  </tr>

  <tr bgcolor="#99CC66">
  <td>&nbsp;</td>
<td colspan="3" id="dateformat" height="20"><a href="../index.html">INDICE</a>&nbsp;&nbsp;::&nbsp;&nbsp;<a href="../arquitectura.html#juegos">JUEGOS&nbsp; </a>::&nbsp;&nbsp;<script language="javascript">
      document.write(TODAY);	</script>	</td>
  </tr>

  <tr>
    <td colspan="4" bgcolor="#99CC66" background="mm_dashed_line.gif"><img src="mm_dashed_line.gif" alt="line decor" width="4" height="3" border="0"></td>
  </tr>

  <tr>
    <td colspan="4" bgcolor="#5C743D"><img src="mm_spacer.gif" alt="" width="1" height="2" border="0"></td>
  </tr>
 <tr>
    <td width="40">&nbsp;</td>
    <td colspan="2" valign="top">&nbsp;<br>
    &nbsp;<br>
    <table border="0" cellspacing="0" cellpadding="2" width="793">
        <tr>
          <td width="789" class="pageName">Blancas vs. Negras</td>
        </tr>
		<tr>
          <td class="bodyText">
			<ul>
				<li><font size="3">Descripción del juego:</font></li>
			</ul>
			<p align="justify">&nbsp;&nbsp;&nbsp; Disponemos de un tablero con 3 
			fichas negras (N), 3 fichas blancas (B) y una casilla vacía, en la 
			siguiente posición inicial:</p>
			<p align="center"><img src="images/blancasynegras.gif" alt="Blancas y negras" width="750" height="145"><br>
            Cada rana representa una ficha de un color.</p>
			<p align="justify">El estado se representa por una tupla de 7 elementos donde cada elemento representa una posición (piedras en la imagen).</p>
			<p align="justify">El objetivo del puzzle consiste en colocar todas las fichas blancas (ranas verdes) 
			  a la izquierda de las fichas negras (ranas marrones), independientemente de la 
			  posición de la casilla vacía. Para ello, los movimientos permitidos 
			  son los siguientes:<br>
			  • Una ficha puede moverse a una celda adyacente vacía, con coste 1.<br>
			  • Una ficha puede desplazarse a una celda vacía saltando dos fichas 
			  como máximo, con un coste igual al número de fichas saltadas.</p>
<ul>
				<li>
				<p align="justify"><font size="3">Heurística:</font></p></li>
			</ul>
			<p align="justify">El objetivo del juego consiste en conseguir que 
			todas las fichas blancas se sitúen a la izquierda de las fichas 
			negras, sin importar la posición de la casilla vacía, ya sea en el 
			centro o en cualquiera de los extremos, por lo que cuanto menor sea 
			el número de fichas blancas a la derecha de la/s ficha/s negra/s 
			menor debe ser el valor heurístico otorgado a ese estado y por lo tanto mas cerca estaremos de la 
			solución.</p>
			<p align="center">h&#39;(x) = Número de fichas Blancas a la derecha de una ficha Negra</p>
			<ul>
				<li>
				<p align="justify"><font size="3">Operadores</font></p></li>
			</ul>
			<p align="justify">Todos los operadores se aplican entre una casilla 
			indicada por el propio operador, que contiene una ficha Blanca o 
			Negra y la casilla vacía.</p>
			<ol>
				<li>
				<p align="justify">Mover hacia la izquierda: Intercambia el 
				valor de la casilla situada a la izquierda de la casilla vacía, 
				por ésta.</p></li>
				<li>
				<p align="justify">Mover hacia la derecha: Intercambia el valor 
				de la casilla situada a la derecha de la casilla vacía, por 
				ésta.</p></li>
				<li>
				<p align="justify">Saltar una ficha hacia la izquierda: 
				Intercambia el valor de la casilla situada dos posiciones a la 
				izquierda de la casilla vacía, por ésta.</p></li>
				<li>
				<p align="justify">Saltar una ficha hacia la derecha: 
				Intercambia el valor de la casilla situada dos posiciones a la 
				derecha de la casilla vacía, por ésta.</p></li>
				<li>
				<p align="justify">Saltar 2 fichas hacia la izquierda: 
				Intercambia el valor de la casilla situada tres posiciones a la 
				izquierda de la casilla vacía, por ésta.</p></li>
				<li>
				<p align="justify">Saltar 2 fichas hacia la derecha: Intercambia 
				el valor de la casilla situada tres posiciones a la derecha de 
				la casilla vacía, por ésta.</p></li>
			</ol>
			<ul>
				<li>
				<p align="justify"><font size="3">Algoritmo</font></p></li>
			</ul>
			<p align="justify">Algoritmo HillClimbingSearch o Escalada Simple: 
			Técnica de búsqueda local más básica. En cada paso, el nodo actual 
			se intenta sustituir por el primer vecino con un valor más alto que 
			el nodo actual o el primer sucesor con una medida heurística mas 
			baja que el nodo actual. Termina cuando encuentra la solución o no 
			puede seguir. Técnica muy dependiente del orden de generación de los 
			hijos.</p>
			<p align="justify">Precisamente la generación de los sucesores hace imposible que el algoritmo de una solución, el primer nodo que genera no puede generar movimiento alguno, pero al tener el mismo valor heurístico que el resto es elegido como primera opción para ser expandido. Al no tener descendientes el problema se queda bloqueado en ese punto.</p>
			<p align="justify">Este es uno de los juegos que hemos puesto que no obtiene una solución del problema.</p>
			<p align="center"><img border="0" src="images/blanca1.jpg"></p>
		  <ul>
				<li>
				<p align="justify"><font size="3">Espacio de estados</font></p>
				</li>
            </ul>
			<p>Estado ( _ , _ , _ , _ , _ , _ , _ ) :- Esta representación nos parece la mas intuitiva ya que nos permite conocer el estado global del juego en cada momento, sin perjudicar en coste ni rendimiento a la búsqueda.</p><p align="justify">Estado inicial:<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( [ Negra, Negra, Negra, Vacía, 
			Blanca, Blanca, Blanca ] )
			
			<p align="justify">Estado final:<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( [ Blanca, Blanca, Blanca, Vacía, Negra, Negra, Negra ] )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( [ Vacía, Blanca, Blanca, Blanca, Negra, Negra, Negra ] )<br>
			&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Estado( [ Blanca, Blanca, Blanca, Negra, Negra, Negra, Vacía ] )<br>
			</td>
		</tr>
		<tr>
          <td class="bodyText"><span class="pageName">Diagrama UML</span></td>
        </tr>
        <tr>
          <td class="bodyText"><p>A continuacion se expone el diagrama uml de este juego para aportar informacion adicional sobre su implementacion.</p>
          <p align="center"><img src="images/UMLBlancasNegras.jpg" alt="UML Blancas y negras" width="750" height="1435"></p></td>
        </tr>
      </table>
  </tr>

 <tr>
    <td width="40">&nbsp;</td>
    <td width="110">&nbsp;</td>
    <td width="494">&nbsp;</td>
	<td width="103">&nbsp;</td>
  </tr>
</table>
</body>
</html>
